package Hot100;

import LinkedList.ListNode;

public class 排序链表 {

    public ListNode sortList(ListNode head) {
        /* 自顶向下归并排序 */
        if (head == null) return null;
        /*return mergeSort(head, null);*/

        /* 自底向上归并排序 */
        int len = 0;
        ListNode cur = head;
        while (cur != null) {
            cur = cur.next;
            len++;
        }
        ListNode dummyHead = new ListNode(-1, head);
        for (int subLen = 1; subLen < len; subLen *= 2) {
            ListNode pre = dummyHead;
            cur = dummyHead.next;
            while (cur != null) {
                ListNode head1 = cur;
                for (int i = 1; i < subLen && cur.next != null; i++) cur = cur.next;
                ListNode head2 = cur.next;
                cur.next = null;
                cur = head2;
                for (int i = 1; i < subLen && cur != null && cur.next != null; i++) cur = cur.next;
                ListNode next = null;
                if (cur != null) {
                    next = cur.next;
                    cur.next = null;
                }
                pre.next = merge(head1, head2);
                while (pre.next != null) pre = pre.next;
                cur = next;
            }
        }
        return dummyHead.next;
    }

    private ListNode mergeSort(ListNode head, ListNode tail) {
        if (head.next == tail) {
            head.next = null;
            return head;
        }
        ListNode slow = head, fast = head;
        while (fast != tail) {
            slow = slow.next;
            fast = fast.next;
            if (fast != tail) fast = fast.next;
        }
        ListNode leftList = mergeSort(head, slow);
        ListNode rightList = mergeSort(slow, tail);
        return merge(leftList, rightList);
    }

    private ListNode merge(ListNode head1, ListNode head2) {
        ListNode dHead = new ListNode(-1);
        ListNode curr = dHead;
        while (head1 != null && head2 != null) {
            if (head1.val <= head2.val) {
                curr.next = head1;
                head1 = head1.next;
            } else {
                curr.next = head2;
                head2 = head2.next;
            }
            curr = curr.next;
        }
        if (head1 != null) curr.next = head1;
        else if (head2 != null) curr.next = head2;
        return dHead.next;
    }
}
